Grokking Meta Coding Interview
Rate this course
Ask Author
Contribute
Back to course home

0% completed

Vote For New Content
Introduction
Who Should Take This Course?
Meta Easy Problems
Toeplitz Matrix (easy)
Solution: Toeplitz Matrix
Remove All Adjacent Duplicates In String (easy)
Solution: Remove All Adjacent Duplicates In String
Minimum Depth of a Binary Tree (easy)
Solution: Minimum Depth of a Binary Tree
Tree Diameter (easy)
Solution: Tree Diameter
Island Perimeter (easy)
Solution: Island Perimeter
Moving Average from Data Stream (easy)
Solution: Moving Average from Data Stream
Move Zeroes (easy)
Solution: Move Zeroes
Missing Ranges (easy)
Solution: Missing Ranges
Palindrome Permutation (easy)
Solution: Palindrome Permutation
Rank Transform of an Array (easy)
Solution: Rank Transform of an Array
Meta Medium Problems
Diagonal Traverse (medium)
Solution: Diagonal Traverse
Shortest Path in Binary Matrix (medium)
Solution: Shortest Path in Binary Matrix
Maximum Swap (medium)
Solution: Maximum Swap
Custom Sort String (medium)
Solution: Custom Sort String
Binary Tree Vertical Order Traversal (medium)
Solution: Binary Tree Vertical Order Traversal
Buildings With an Ocean View (medium)
Solution: Buildings With an Ocean View
Basic Calculator II (medium)
Solution: Basic Calculator II
Nested List Weight Sum (medium)
Solution: Nested List Weight Sum
Dot Product of Two Sparse Vectors (medium)
Solution: Dot Product of Two Sparse Vectors
Max Consecutive Ones III (medium)
Solution: Max Consecutive Ones III
Subarray Sum Equals K (medium)
Solution: Subarray Sum Equals K
Next Permutation (medium)
Solution: Next Permutation
Simplify Path (medium)
Solution: Simplify Path
Lowest Common Ancestor of a Binary Search Tree (medium)
Solution: Lowest Common Ancestor of a Binary Search Tree
'K' Closest Points to the Origin (medium)
Solution: 'K' Closest Points to the Origin
Sum of Path Numbers (medium)
Solution: Sum of Path Numbers
Merge Intervals (medium)
Solution: Merge Intervals
Right View of a Binary Tree (medium)
Solution: Right View of a Binary Tree
Number of Islands (medium)
Solution: Number of Islands
Clone Graph (medium)
Solution: Clone Graph
Missing Element in Sorted Array (medium)
Solution: Missing Element in Sorted Array
Number of Substrings Containing All Three Characters (medium)
Solution: Number of Substrings Containing All Three Characters
Capacity To Ship Packages Within D Days (medium)
Solution: Capacity To Ship Packages Within D Days
Count and Say (medium)
Solution: Count and Say
Contiguous Array (medium)
Solution: Contiguous Array
Meta Hard Problems
Sliding Window Median (hard)
Solution: Sliding Window Median
Alien Dictionary (hard)
Solution: Alien Dictionary
Minimum Window Substring (hard)
Solution: Minimum Window Substring
Best Meeting Point (hard)
Solution: Best Meeting Point
Maximum Sum of 3 Non-Overlapping Subarrays (hard)
Solution: Maximum Sum of 3 Non-Overlapping Subarrays
Making A Large Island (hard)
Solution: Making A Large Island
Basic Calculator (Hard)
Solution: Basic Calculator
Serialize and Deserialize Binary Tree (hard)
Solution: Serialize and Deserialize Binary Tree
Longest Increasing Path in a Matrix (hard)
Solution: Longest Increasing Path in a Matrix
Valid Palindrome III (hard)
Solution: Valid Palindrome III
Solution: Minimum Window Substring

Problem Statement

Given a string s and t of length m and n respectively, find the smallest substring in a given string 's' that contains all the characters (including duplicate) of another string 't'. The order of characters in 't' doesn't matter, but the substring in 's' must include all characters of 't', possibly with additional characters.

If no such substring exists, return an empty string.

Examples

Example 1:

  • Input: s = "xyyzyzyx", t = "xyz"
  • Expected Output: "zyx"
  • Justification: "zyx" is the shortest substring of 's' that contains 'x', 'y', and 'z'.

Example 2:

  • Input: s = "abracadabra", t = "aa"
  • Expected Output: "ada"
  • Justification: "ada" at the end of 's' is the shortest substring containing all 'a's in 't'.

Example 3:

  • Input: s = "welcomeback", t = "ole"
  • Expected Output: "elco"
  • Justification: "elco" includes 'o', 'l', and 'e', fulfilling the requirements with the minimum length.

Solution

To solve this problem, we'll use a sliding window approach combined with a character frequency map. This approach is efficient because it involves scanning the string 's' only once while adjusting the window's start and end to include all characters of 't'.

Initially, we'll create a map to keep track of the frequency of each character in 't'. As we traverse 's', we'll adjust the end of the window to include characters and decrease their frequency in the map. Once all characters from 't' are included in the window, we'll attempt to shrink the window from the start, checking if it still contains all necessary characters. This approach ensures we always have the minimum window containing all characters of 't', which is the core requirement of the problem.

Step-by-step Algorithm

  • Initialize a map to store the frequency of each character in 't'.
  • Use two pointers, start and end, to represent the current window in 's'.
  • Iterate over 's' using the end pointer.
    • For each character in 's' at end, decrease its frequency in the map.
    • Once all characters from 't' are included in the current window (checked via the map), try to shrink the window.
      • Move the start pointer forward while the window still contains all characters from 't'.
    • Update the minimum window size and its starting index when a smaller valid window is found.
  • Return the smallest valid substring from 's' based on the recorded starting index and size. If no such window exists, return an empty string.

Algorithm Walkthrough

Let's take "xyyzyzyx" as 's' and "xyz" as 't'.

Initialization:

  • Map Creation: Create a frequency map for characters in t. Map: {x: 1, y: 1, z: 1}.
  • Variable Initialization: Set start and end to 0, minStart to 0, minLength to a large value (like Integer.MAX_VALUE), and counter to the length of t, which is 3.
  1. First Expansion:

    • end = 0, s[end] = 'x'. Map: {x: 0, y: 1, z: 1}, counter = 2. Window: "x".
  2. Second Expansion:

    • end = 1, s[end] = 'y'. Map: {x: 0, y: 0, z: 1}, counter = 1. Window: "xy".
  3. Third Expansion:

    • end = 2, s[end] = 'y'. Map: {x: 0, y: -1, z: 1}. Window: "xyy".
  4. Fourth Expansion:

    • end = 3, s[end] = 'z'. Map: {x: 0, y: -1, z: 0}, counter = 0. Window: "xyyz".
  5. Start Shrinking:

    • start = 1, s[start - 1] = 'x'. Map: {x: 1, y: -1, z: 0}. Window: "yyz".
  6. Fifth Expansion:

    • end = 4, s[end] = 'y'. Map: {x: 1, y: -2, z: 0}. Window: "yyzy".
  7. Sixth Expansion:

    • end = 5, s[end] = 'z'. Map: {x: 1, y: -2, z: -1}. Window: "yyzyz".
  8. Seventh Expansion:

    • end = 6, s[end] = 'y'. Map: {x: 1, y: -3, z: -1}. Window: "yyzyzy".
  9. Eighth Expansion:

    • end = 7, s[end] = 'x'. Map: {x: 0, y: -3, z: -1}. Window: "yzyzyx".
    • Current window contains all characters of string t. minLength: min(4, 6) = 4, minStart: 2.
    • start is now incremented to find a smaller window containing all characters.
  10. Shrinking Again:

    • Shrink: start=2, end=7, Window: "yzyzyx", Map: {x: 0, y: -2, z: -1}, Counter remains 0.
    • Shrink: start=3, end=7, Window: "zyzyx", Map: {x: 0, y: -1, z: -1}, Counter remains 0.
    • Shrink: start=4, end=7, Window: "yzyx", Map: Map: {x: 0, y: -1, z: 0}, Counter remains 0.
    • Shrink: start=5, end=7, Window: "zyx", Map: {x: 0; y: 0, z: 0}, Counter becomes 1.
    • This is the smallest window that contains all characters of t.

Result:

  • The minimum window substring that contains all characters of t ("xyz") is "zyx".

Code

Java
Saved to Cloud

. . . .

Complexity Analysis

Time Complexity

The time complexity is O(S + T), where S is the length of string s and T is the length of string t.

This is because the algorithm iterates through both strings linearly. The outer loop runs for every character in s, and the inner while loop processes each character only once when shrinking the window.

Space Complexity

The space complexity is O(T), where T is the length of string t.

This complexity arises from the storage required for the frequency map of characters in t. In the worst case, this map will store a distinct entry for each character in t.

Minimum Window Substring (hard)
Best Meeting Point (hard)
Mark as Completed

On this page

Problem Statement

Examples

Solution

Step-by-step Algorithm

Algorithm Walkthrough

Code

Complexity Analysis

Time Complexity

Space Complexity